package Midium;

import java.util.*;

// 554. 砖墙
/*
 * 对于每一行，将砖块转换为数字 [1,2,2,1]  ->  [1,3,5,6]
 * 把每一行都转换完以后，遍历[1,5]每一列，找出一条竖线使穿过的砖头最小
 * 对于每一列，如果有一行存在对应列数的数字，则表示经过此行没有穿过砖头
 * -------------------------------------------------------
 * 代码超时
 * 当wall == [[100000000],[100000000],[100000000]]时，还从1遍历到100000000，显然是浪费时间
 * 优化方法：
 * 不从1开始遍历，只遍历出现过的数字，因为如果数字没出现，代表根本不可能在这一列减去1
 * -------------------------------------------------------
 * 代码超时
 * 优化方法：
 * 把set换成map，直接记录每个set值对应的数量，避免还要从set里找出哪个值出现的次数最多
 * */
public class Solution554 {
    public static int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (List<Integer> list : wall) {
            for (int i = 0; i < list.size(); i++) {
                if (i != 0)
                    list.set(i, list.get(i - 1) + list.get(i));
                // 最后一个数不加入
                if (i != list.size() - 1) {
                    if (map.containsKey(list.get(i))) {
                        map.replace(list.get(i), map.get(list.get(i)) + 1);
                    } else {
                        map.put(list.get(i), 1);
                    }
                }
            }
        }
        // 寻找最大的value
        int max = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            max = Math.max(max, entry.getValue());
        }
        return wall.size() - max;
    }

    public static void main(String[] args) {
//        ArrayList object1 = new ArrayList<>();
//        ArrayList object2 = new ArrayList<>();
//        ArrayList object3 = new ArrayList<>();
//        ArrayList object4 = new ArrayList<>();
//        ArrayList object5 = new ArrayList<>();
//        ArrayList object6 = new ArrayList<>();
//        object1.add(1);
//        object1.add(2);
//        object1.add(2);
//        object1.add(1);
//        object2.add(3);
//        object2.add(1);
//        object2.add(2);
//        object3.add(1);
//        object3.add(3);
//        object3.add(2);
//        object4.add(2);
//        object4.add(4);
//        object5.add(3);
//        object5.add(1);
//        object5.add(2);
//        object6.add(1);
//        object6.add(3);
//        object6.add(1);
//        object6.add(1);
//        List list = new ArrayList();
//        list.add(object1);
//        list.add(object2);
//        list.add(object3);
//        list.add(object4);
//        list.add(object5);
//        list.add(object6);
        List list = new ArrayList();
        List o1 = new ArrayList();
        List o2 = new ArrayList();
        List o3 = new ArrayList();
        o1.add(1);
        o1.add(1);
        o2.add(2);
        o3.add(1);
        o3.add(1);
        list.add(o1);
        list.add(o3);
        list.add(o2);
        System.out.println(leastBricks(list));
    }
}
